package com.gxd.item_33;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
 * 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.
 *
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
 */
public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("invalid param");
        }

        if (nums.length == 1) {
            return target == nums[0] ? 0 : -1;
        }

        int start = 0, end = nums.length - 1;
        while (start <= end) {
            int middle = (start + end) / 2;

            if (nums[middle] == target) {
                return middle;
            }

            if (nums[0] <= nums[middle]) {
                if (nums[0] <= target && target < nums[middle]) {
                    end = middle - 1;
                } else {
                    start = middle + 1;
                }
            } else {
                if (nums[middle] < target && target <= nums[nums.length - 1]) {
                    start = middle + 1;
                } else {
                    end = middle - 1;
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // 0 1 2 4 5 6 7

        int[] nums = {4,5,6,7,0,1,2};
        int target = 0;

        System.out.println(solution.search(nums, target));
    }
}
